package org.usmile.algorithms.learn.sort;

import java.util.Arrays;

/**
 * 基数排序
 */
@SuppressWarnings("all")
public class RadixSorter {
    public void sort(int[] nums) {
        if (nums == null || nums.length <= 1) {
            return;
        }

        int max = nums[0];
        for (int num : nums) {
            if (num > max) {
                max = num;
            }
        }

        for (int exp = 1; exp <= max; exp *= 10) {
            countSort(nums, exp);
        }
    }

    private void countSort(int[] nums, int exp) {
        int[] count = new int[10];
        for (int num : nums) {
            int digit = (num / exp) % 10;
            count[digit]++;
        }

        for (int i = 1; i < 10; i ++) {
            count[i] += count[i - 1];
        }

        int[] temp = new int[nums.length];
        for (int i = nums.length - 1; i >= 0; i--) {
            int digit = (nums[i] / exp) % 10;
            temp[count[digit]-- - 1] = nums[i];
        }

        for (int i = 0; i < nums.length; i ++) {
            nums[i] = temp[i];
        }
    }

    public static void main(String[] args) {
        int[] data = new int[]{4512, 4231, 31923, 2165, 1141, 1, 10, 9, 22, 29};
        new RadixSorter().sort(data);
        System.out.println(Arrays.toString(data));
    }
}
